using JufGame.Collections.Generic;
using System;
using System.Collections.Generic;

namespace JufGame.AI
{
	public interface IAStarNode<T> where T : IAStarNode<T>
	{
        public T Parent { get; set; }
        public float SelfCost { get; set; }
        public float GCost { get; set; }//距初始状态的代价
        public float HCost { get; set; }//距目标状态的代价
        public float FCost { get; }
        /// <summary>
        /// 获取与指定节点的预测代价
        /// </summary>
        public float GetDistance(T otherNode);
		/// <summary>
		/// 获取后继（邻居）节点
		/// </summary>
        /// <param name="nodeMap">寻路所在的地图，类型看具体情况转换，
        /// 故用object类型</param>
        /// <returns>后继节点列表</returns>
		public List<T> GetSuccessors(object nodeMap);
        /* 一般比较可用以下函数
        public int CompareTo(AStarNode other)
        {
        	var res = (int)(FCost - other.FCost);
			if(res == 0)
				res = (int)(HCost - other.HCost);
			return res;
        }
        */
	}
    /// <summary>
    /// A星搜索器
    /// </summary>
    /// <typeparam name="T_Map">搜索的图类</typeparam>
    /// <typeparam name="T_Node">搜索的节点类</typeparam>
	public class AStar_Searcher<T_Map, T_Node> where T_Node: IAStarNode<T_Node>, IComparable<T_Node>
	{
        private readonly HashSet<T_Node> closeList;//探索集
        private readonly MyHeap<T_Node> openList;//边缘集
        private readonly T_Map nodeMap;//搜索空间（地图）
        public AStar_Searcher(T_Map map, int maxNodeSize = 200)
        {
            nodeMap = map;
            closeList = new HashSet<T_Node>();
            //maxNodeSize用于限制路径节点的上限，避免陷入无止境搜索的情况
            openList = new MyHeap<T_Node>(maxNodeSize);
        }
        /// <summary>
        /// 搜索（寻路）
        /// </summary>
        /// <param name="start">起点</param>
        /// <param name="target">终点</param>
        /// <param name="pathRes">返回生成的路径</param>
        public void FindPath(T_Node start, T_Node target, Stack<T_Node> pathRes)
        {
            T_Node currentNode;
            pathRes.Clear();//清空路径以备存储新的路径
            closeList.Clear();
            openList.Clear();
            openList.PushHeap(start);
            while (!openList.IsEmpty)
            {
                currentNode = openList.Top;//取出边缘集中最小代价的节点
                openList.PopHeap();
                closeList.Add(currentNode);//拟定移动到该节点，将其放入探索集
                if (currentNode.Equals(target) || openList.IsFull)//如果找到了或图都搜完了也没找到时
                {
                    GenerateFinalPath(start, currentNode, pathRes);//生成路径并保存到pathRes中
                    return;
                }
                UpdateList(currentNode, target);//更新边缘集和探索集
            }
            return;
        }
        private void GenerateFinalPath(T_Node startNode, T_Node endNode, Stack<T_Node> pathStack)
        {
            pathStack.Push(endNode);//因为回溯，所以用栈储存生成的路径
            var tpNode = endNode.Parent;
            while (!tpNode.Equals(startNode))
            {
                pathStack.Push(tpNode);
                tpNode = tpNode.Parent;
            }
            pathStack.Push(startNode);
        }
        private void UpdateList(T_Node curNode, T_Node endNode)
        {
            T_Node sucNode;
            float tpCost;
            bool isNotInOpenList;
            var successors = curNode.GetSuccessors(nodeMap);//找出当前节点的后继节点
            for (int i = 0; i < successors.Count; ++i)
            {
                sucNode = successors[i];
                if (closeList.Contains(sucNode))//后继节点已被探索过就忽略
                    continue;
                tpCost = curNode.GCost + sucNode.SelfCost;
                isNotInOpenList = !openList.Contains(sucNode);
                if (isNotInOpenList || tpCost < sucNode.GCost)
                {
                    sucNode.GCost = tpCost;
                    sucNode.HCost = sucNode.GetDistance(endNode);//计算启发函数估计值
                    sucNode.Parent = curNode;//记录父节点，方便回溯
                    if (isNotInOpenList)
                    {
                        openList.PushHeap(sucNode);
                    }
                }
            }
        }
    }
}
